package 回溯;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 首先进行一下题目描述！
 * 给你一个 只有 数字 组成的 字符串！ （0  ~  9）
 * 1 --> A, 2---> B
 * 10---> J
 * 以此类推! 请收集, 所有的转换成   大写字母 的字符串的集合! 
  * @author I adore you
  * 
  * 再改成 动态规划!
 */
public class 左FaceBook {
	
	
	public static void main(String []args) {
		String s ="12324222232516";
		System.out.println(new 左FaceBook().solution(s).size());
		char str[] = s.toCharArray();
		int len  = str.length;
//		System.out.println((char)('Z' + 1));
		System.out.println(dfs(str,len,0));
		System.out.println(dp(str));
	}
	
	public List<Deque<Character>> solution(String str){
		List<Deque<Character>> ans = new ArrayList<>();
		Deque<Character> path = new ArrayDeque<>();
		if(str == null)
			return ans;
		char [] s = str.toCharArray();
		int len = s.length;
		process(s,len,ans,0,path);
		return ans;
	}
	
	/**
	 * 这里 考虑 一下特殊的 数字   0
	 * 注意: 是不能以 0 作为开头的, 0 只能在中间,或者 末尾,
	 * 比如   '01234' 这就是一个无效的字符串!  而 '102030', 类似于这种就是有效的字符串!
	 * 每一层递归 都是同样的 考虑策略!
	 * 以  i 开头  
	*以 i + 1 开头
	*只能是上面两种情况!
	*因为转化的范围, 只能是  '1 ~ 26'  ------> 'A ~ Z'
	*主要有三种的 讨论情况!
	* 以  0 开头  直接return
	* 以 1 开头   单独 以 1 开头, 或者 以  1x 开头
	* 以 2 开头  单独 以 2 开头, 或者 以 2x 开头(这个是条件的 20 ~ 26(之间才可以) , )
	* 以 other 开头  只能单独, 以 other 开头
	*
	 */
	public void process(char [] s,int len,List<Deque<Character>> ans,int index,Deque<Character> path) {
		if(index == len) {
			ans.add(new ArrayDeque<>(path));
			return ;
		}
		if(s[index] == '0') {
			// 表示 以 0 开头, 但是不能 以 0 开头,这里注意一下;
			return ;
		}
		if(s[index] == '1') {
			// 单独开头
			path.addLast('A');
			process(s,len,ans,index + 1,path);
			// 回溯一下
			path.removeLast();
			//两位 开头
			if(index + 1 < len ) {
//				'A' + ((s[index] - '0') * 10 + (s[index + 1] - '0')) 
				path.addLast((char)('A' - 1  +  ((s[index] - '0') * 10 + (s[index + 1] - '0'))));
				process(s,len,ans,index + 2,path);
				// 这个撤销的操作还是 写上 微妙!, 否则可能结果就不正确了!
				path.removeLast();
			}	
		}
		else if(s[index] == '2') {
			// 单独开头
			path.addLast('B');
			process(s,len,ans,index + 1,path);
			// 回溯一下
			path.removeLast();
			//两位 开头
//			char temp = ;
			if(index + 1 < len && (char)('A' - 1  +  ((s[index] - '0') * 10 + (s[index + 1] - '0'))) <= 'Z' ) {
//				'A' + ((s[index] - '0') * 10 + (s[index + 1] - '0')) 
				path.addLast((char)('A' - 1  +  ((s[index] - '0') * 10 + (s[index + 1] - '0'))));
				process(s,len,ans,index + 2,path);
				// 这个撤销的操作还是 写上 微妙!, 否则可能结果就不正确了!
				path.removeLast();
			}

		}
		else {
			// 这种情况只能 单独开头
			path.addLast((char)(s[index] - '0' + 'A' - 1));
			process(s,len,ans,index + 1,path);
			// 回溯一下!
			path.removeLast();
		}
	}
   /**
     * 稍微 改造 一下：改造成 dp 的问题 
    *返回 ，所有的 可能  转换的  结 果 数！
    *下面这种 思维逻辑写的 还是 很吊的！
    *牛逼！
    *注意 这种 和 lc 93 赋值 ip 地址 的一些区别 
    *区别 就是 ： 收集 结果的 时候 ，lc 93 还需要一些 额外的 判断， 多说无益 ，多去思考 就明白了！
    */
	public static int dfs(char [] s,int len,int index) {
		if(index == len) {
			// 能到达这里， 说明这就是 一个 结果！
			return 1;
		}
		// 以 0 开头 ，没有 结果
		if(s[index] == '0')
			return 0;
		int ans = 0;
		// 1 ~ 9 都能单独 作为 开头 ，这里直接提出来了！
		ans += dfs(s,len,index + 1);
		// 能 两位 开头的 只有  1 和 2 ，所以只对这两个 判断 就行了！
		if(index + 1 < len && (s[index] - '0') * 10 + s[index + 1] - '0' <= 26)
			ans += dfs(s,len,index + 2);
		return ans;
	}
	
	/**
	 * 改成 dp 版本 
	 */
	public static int dp(char []s ) {
		int len  = s.length;
		int dp [] = new int [len + 1];
		// 初始化 basecase
		dp[len] = 1;
		for(int index = len - 1;index >= 0;index--) {
			dp[index] = dp[index + 1];
			if(index + 1 < len && (s[index] - '0') * 10 + s[index + 1] - '0' <= 26 )
				dp[index] += dp[index + 2];
		}
		return dp[0];
	}
}
